package auggen;

//by Andrew Leach
	

import java.util.*;
import java.io.*;
import org.apache.commons.math.fraction.BigFraction;

public class generator {
	static ArrayList<LineSegment> linesegs = new ArrayList<LineSegment>();
	static Random rdm = new Random();
	
	//determines location to print text file
	static String filelocation = "/home/ableach/sketchbook/networkdraw/GSS/generated1.txt";
	
	//segnum is the number of line segments, it is also
	//the horizontal and vertical grid length
	static int segnum = 20;
	
	//assign probabilities to various line segment generation methods
	static double probRandomSeg = .6;
	static double probVertToVert = .2;
	static double probVertToRandom = .2;
	
	
	public static void main(String args[]){
		//create first line segment
		linesegs.add(new LineSegment("s0",new BigFraction(rdm.nextInt(segnum)), new BigFraction(rdm.nextInt(segnum)),
				new BigFraction(rdm.nextInt(segnum)), new BigFraction(rdm.nextInt(segnum))));
		 
		//creates 3 more line segs, to allow VertToVert
		for(int j = 1; j<=3; j++){
			linesegs.add(randomSeg(linesegs, j));
		}
		
		//continue until fully populated
		for(int i = 4;linesegs.size()!=segnum; i++){
			double createType = Math.random();
			
			
			//creates a random segment if chosen
			if(createType <= probRandomSeg){
				linesegs.add(randomSeg(linesegs, i));
			}
			
			
			//connects a vertex to a vertex if chosen
			else if(createType < probRandomSeg + probVertToVert){
				linesegs.add(vertToVert(linesegs, i));
			}
			
			//creates a random segment with a vertex as a firstpt if chosen
			else{
				linesegs.add(randomToVert(linesegs, i));
			}
						
			
		}
		// delete me !!! this is for testing only!!
		for(int r = 0; r<linesegs.size(); r++){
			System.out.println(linesegs.get(r).toString());
		}
		//to print the line segments to a text file
		try{
			
			FileWriter filewrite = new FileWriter(filelocation);
			BufferedWriter fileout = new BufferedWriter(filewrite);
			for(int i = 0; i < linesegs.size(); i++){
				LineSegment templine = linesegs.get(i);
				fileout.write(templine.getX1()+" "+
						templine.getY1()+" "+ templine.getX2()+" "+templine.getY2());
				fileout.newLine();
			}
			fileout.close();
		}
		catch (Exception e){
            System.err.println("Error: " + e.getMessage());
        }		
	}//end main
	
	//returns true if a point is greater than a line segment
	public static boolean greaterThanLine(BigFraction x, BigFraction y, LineSegment seg){
		//handle normal line
		if(seg.isNotVertical()){
			if(seg.yValue(x).compareTo(y)==1){
				return false;
			}
		}
		//handle vertical line
		else{
			if(seg.getX1().compareTo(x)==1){
				return false;
			}
		}
		return true;
	}
	
	//returns true if a point is greater than a line segment
	public static boolean lessThanLine(BigFraction x, BigFraction y, LineSegment seg){
		//handle normal line
		if(seg.isNotVertical()){
			if(seg.yValue(x).compareTo(y)==-1){
				return false;
			}
		}
		//handle vertical line
		else{
			if(seg.getX1().compareTo(x)==-1){
				return false;
			}
		}
		return true;
	}
	
	//returns the first endpoint of a new line segment
	public static Point chooseFirstPt(){
		int sindex = rdm.nextInt(linesegs.size());		
		LineSegment seg = linesegs.get(sindex);
		BigFraction x = new BigFraction(rdm.nextInt(segnum));
		BigFraction y = new BigFraction(rdm.nextInt(segnum));
		
		//handle normal line
		if(seg.isNotVertical()){
			if(seg.yValue(x).equals(y)){
				return chooseFirstPt();
			}
			else{
				Point point = new Point(x,y,seg);
				return point;
			}
		}
		
		//handle vertical line
		else{
			if(seg.getX1()==x){
				return chooseFirstPt();
			}
			else{
				Point point = new Point(x,y,seg);
				return point;
			}
		}
	}
	
	//finds y value for a line at a given x. Needed to avoid creating
	//new unnecessary line segments in method chooseSecondPt()
	public static BigFraction yValue(BigFraction x, BigFraction X1, BigFraction Y1, BigFraction X2, BigFraction Y2){
		if(X1!=X2){
			//(Y2-Y1)*x/(X2-X1)+Y1-(X1*(Y2-Y1)/(X2-X1));
			return (Y2.subtract(Y1)).multiply(x.divide(X2.subtract(X1))).add(Y1.subtract(X1.multiply(Y2.subtract(Y1)).divide(X2.subtract(X1)))); 
		}
		else{
			return new BigFraction(0);
		}
      }
	
	//define greaterThanLine() method for points, same reasoning as above
	public static boolean greaterThan(BigFraction x, BigFraction y, BigFraction X1, BigFraction Y1, BigFraction X2, BigFraction Y2){
		//handles normal line 
		if(!X1.equals(X2)){
			 // if(((Y2-Y1)*x/(X2-X1)+Y1-(X1*(Y2-Y1)/(X2-X1)))>y)
			 if((Y2.subtract(Y1)).multiply(x.divide(X2.subtract(X1))).
					 add(Y1.subtract(X1.multiply(Y2.subtract(Y1)).divide(X2.subtract(X1)))).compareTo(y)==1){
				 return false;
			 }
		}
		//handles vertical line
		else{
			if(X1.compareTo(x)==1){
				return false;
			}
		}
		return true;
      }
	
	//define lessThanLine() method for points, same reasoning as above
	public static boolean lessThan(BigFraction x, BigFraction y, BigFraction X1, BigFraction Y1, BigFraction X2, BigFraction Y2){
		//handles normal line 
		if(!X1.equals(X2)){
			 if((Y2.subtract(Y1)).multiply(x.divide(X2.subtract(X1))).
					 add(Y1.subtract(X1.multiply(Y2.subtract(Y1)).divide(X2.subtract(X1)))).compareTo(y)==-1){
				 return false;
			 }
		}
		//handles vertical line
		else{
			if(X1.compareTo(x)==-1){
				return false;
			}
		}
		return true;
      }
	
	
	//choose second point of a new line segment in a way such that it must intersect atleast
	// one other line segment
	public static Point chooseSecondPt(Point firstpt){
		LineSegment seg = firstpt.getSeg();
		ArrayList<Point> candidates = new ArrayList<Point>();
		
		//sets doubles for ease of use, ordered by least x
		BigFraction X1,Y1,X2,Y2;
		if(seg.getX1().compareTo(seg.getX2())==-1){
			X1 = seg.getX1();
			Y1 = seg.getY1();
			X2 = seg.getX2();
			Y2 = seg.getY2();			
		}
		else{
			X2 = seg.getX1();
			Y2 = seg.getY1();
			X1 = seg.getX2();
			Y1 = seg.getY2();
		}
		
		//xp and yp are coords of first pt
		
		BigFraction xp = firstpt.getX();
		BigFraction yp = firstpt.getY();
		
		//tests a random point
		BigFraction x = new BigFraction(rdm.nextInt(segnum));
		BigFraction y = new BigFraction(rdm.nextInt(segnum));
		
		
		
		//handles the case where the segment is not vertical
		if(seg.isNotVertical()){
			//here there are three cases, the first point is to the left of endpoints, 
			//between endpoints, or to the right of endpoints
			
			//case where first point is to the left of the segment
			if(xp.compareTo(X1)<=0){
				
				//handles the case where the point is greater than the seg
				if(greaterThanLine(xp, yp, seg)){							
					if(lessThanLine(x,y,seg)&& greaterThan(x, y, xp, yp, X1, Y1)
							&& lessThan(x, y, xp, yp, X2, Y2)){
						Point testpt = new Point(x, y, seg);
						candidates.add(testpt);
					}
					else{return chooseSecondPt(firstpt);}
				}
			
				//handles the case where the point is less than the seg.
				else{
					if(greaterThanLine(x,y, seg)&& lessThan(x, y, xp, yp, X1, Y1)
							&&	greaterThan(x, y, xp, yp, X2, Y2)){
						Point testpt = new Point(x, y, seg);
						candidates.add(testpt);
					}
					else{return chooseSecondPt(firstpt);}
				}			
			}
			
			//case where first point is to the right of the segment
			else if(firstpt.getX().compareTo(Max(seg.getX1(),seg.getX2()))==1){
				
				//handles the case where the point is greater than the seg
				if(greaterThanLine(xp, yp, seg)){
					if(lessThanLine(x, y, seg)&& lessThan(x, y, xp, yp, X1, Y1)
							&& greaterThan(x, y, xp, yp, X2, Y2)){
						Point testpt = new Point(x, y, seg);
						candidates.add(testpt);
					}
					else{return chooseSecondPt(firstpt);}
				}
			
				//handles the case where the point is less than the seg.
				else{
					if(greaterThanLine(x, y, seg)&&	greaterThan(x, y, xp, yp, X1, Y1)
							&& lessThan(x, y, xp, yp, X2, Y2)){
						Point testpt = new Point(x, y, seg);
						candidates.add(testpt);
					}
					else{return chooseSecondPt(firstpt);}
				}
			}
			
			//case where first point is in between endpoints of the segment
			else{			
				
				//handles the case where the point is greater than the seg
				if(greaterThanLine(firstpt.getX(), firstpt.getY(), seg)){
					if(lessThanLine(x, y, seg)&	lessThan(x, y, xp, yp, X1, Y1)
							&& lessThan(x, y, xp, yp, X2, Y2)){
						Point testpt = new Point(x, y, seg);
						candidates.add(testpt);
					}
					else{return chooseSecondPt(firstpt);}
				}
			
				//handles the case where the point is less than the seg.
				else{
					if(greaterThanLine(x, y, seg)&& greaterThan(x, y, xp, yp, X1, Y1)
							&& greaterThan(x, y, xp, yp, X2, Y2)){
						Point testpt = new Point(x, y, seg);
						candidates.add(testpt);
					}
					else{return chooseSecondPt(firstpt);}
				}
			}
		}	
		
		//handles the case where the segment is vertical
		else{
			
			//point is on right of vertical segment
			if(firstpt.getX().compareTo(seg.getX1())==1){
				if(lessThanLine(x, y, seg)&& lessThan(x, y, xp, yp, X1, Max(Y1, Y2))
						&& greaterThan(x, y, xp, yp, X1, Min(Y1, Y2))){
					Point testpt = new Point(x, y, seg);
					candidates.add(testpt);
				}
				else{return chooseSecondPt(firstpt);}
			}
			
			//point is on left of vertical segment
			else{
				if(greaterThanLine(x, y, seg)&& lessThan(x, y, xp, yp, X1, Max(Y1, Y2))
						&& greaterThan(x, y, xp, yp, X1, Min(Y1, Y2))){
					Point testpt = new Point(x, y, seg);
					candidates.add(testpt);
				}
				else{return chooseSecondPt(firstpt);}
			}
		}
		
		int dindex = rdm.nextInt(candidates.size());
		Point toadd = candidates.get(dindex);
		return toadd;
	}
	
	
	//test to see if the two points would form a line segment that overlaps another
	public static boolean isLegal(Point pointa, Point pointb){
		BigFraction X1 = pointa.getX();
		BigFraction Y1 = pointa.getY();
		BigFraction X2 = pointb.getX();
		BigFraction Y2 = pointb.getY();
		
		for(int i = 0; i < linesegs.size(); i++){
			LineSegment tempseg = linesegs.get(i);
			BigFraction xp1 = tempseg.getX1();
			BigFraction yp1 = tempseg.getY1();
			BigFraction xp2 = tempseg.getX2();
			BigFraction yp2 = tempseg.getY2();
			
			
			
			//handles case where line is not vertical
			if(!X1.equals(X2)){			
				
				//if a line has the same slope as the two points and the same roots
				if(((tempseg.slope()).abs()==(Y2.subtract(Y1).divide(X2.subtract(X1))).abs())
						&& (tempseg.yValue(X1)==Y1)){
					
					//if one of the points is in the interval of the segment
					if(((Min(xp1, xp2).compareTo(X1)<=0 && (Max(xp1, xp2).compareTo(X1)>=0))
							||((Min(xp1, xp2).compareTo(X2)<=0) && (Max(xp1, xp2).compareTo(X2)>=0 )))){
						return false;
					}
				}
			}
			//handles the case where the line is vertical
			else{
				if(((Min(yp1, yp2)).compareTo(Y1)<=0) && (Max(yp1, yp2).compareTo(Y1)>=0)
						|| (Min(yp1, yp2).compareTo(Y2)<=0 && (Max(yp1, yp2).compareTo(Y2)>=0))){
					return false;
				}						
			}
		}
		return true;
	}
	
	
	
	//checks if two line segments intersect by mdm32
	public static boolean doIntersect(LineSegment a, LineSegment b){
        BigFraction x1 = a.getX1();
        BigFraction y1 = a.getY1();
        BigFraction x2 = a.getX2();
        BigFraction y2 = a.getY2();
        BigFraction x3 = b.getX1();
        BigFraction y3 = b.getY1();
        BigFraction x4 = b.getX2();
        BigFraction y4 = b.getY2();
        
        if(a.yValue(x3).equals(y3) && ((x1.compareTo(x3)<=0 && x2.compareTo(x3)>=0) ||
                ((x1.compareTo(x3)>=0 && x2.compareTo(x3)<=0)))){
            return true;
        }
        if(a.yValue(x4).equals(y4) && ((x1.compareTo(x4)<=0 && x2.compareTo(x4)>=0) ||
                ((x1.compareTo(x4)>=0 && x2.compareTo(x4)<=0)))){
            return true;
        }
        if(b.yValue(x1).equals(y1) && ((x3.compareTo(x1)<=0 && x4.compareTo(x1)>=0) ||
                ((x3.compareTo(x1)>=0 && x4.compareTo(x1)<=0)))){
            return true;
        }
        if(b.yValue(x2).equals(y2) && ((x3.compareTo(x2)<=0 && x4.compareTo(x2)>=0) ||
                ((x3.compareTo(x2)>=0 && x4.compareTo(x2)<=0)))){
            return true;
        }


        //double det123 = (x2 - x1)*(y3 - y1) - (x3 - x1)*(y2 - y1);
        BigFraction det123 = ((x2.subtract(x1)).multiply(y3.subtract(y1))).subtract((x3.subtract(x1)).multiply(y2.subtract(y1)));
        //double det124 = (x2 - x1)*(y4 - y1) - (x4 - x1)*(y2 - y1);
        BigFraction det124 = ((x2.subtract(x1)).multiply(y4.subtract(y1))).subtract((x4.subtract(x1)).multiply(y2.subtract(y1)));
        //double det341 = (x3 - x1)*(y4 - y1) - (x4 - x1)*(y3 - y1);
        BigFraction det341 = ((x3.subtract(x1)).multiply(y4.subtract(y1))).subtract((x4.subtract(x1)).multiply(y3.subtract(y1)));

        BigFraction det342 = det123.subtract(det124).add(det341);

        BigFraction zero = new BigFraction(0);

        if((det123.multiply(det124)).compareTo(zero)==-1 && (det341.multiply(det342)).compareTo(zero)==-1)
            return true;
        if((det123.multiply(det124)).equals(zero) && (det341.multiply(det342)).equals(zero))
            return true;

        return false;
    }

	
	//creates a point at intersection points by mdm32
	//modified by Andrew Leach to return a point rather than a vertex
	public static Point intersection(LineSegment a, LineSegment b){
        BigFraction x = new BigFraction(0);
        BigFraction y = new BigFraction(0);

        BigFraction x1 = a.getX1();
        BigFraction y1 = a.getY1();
        BigFraction x2 = a.getX2();
        BigFraction y2 = a.getY2();
        BigFraction x3 = b.getX1();
        BigFraction y3 = b.getY1();
        BigFraction x4 = b.getX2();
        BigFraction y4 = b.getY2();


        Vector<String> segs = new Vector<String>();
        segs.add(a.getName());
        segs.add(b.getName());


        if(x1.equals(x2)){
            x=x1;
            BigFraction s2 = (y4.subtract(y3)).divide(x4.subtract(x3));
            y=s2.multiply(x.subtract(x3)).add(y3);
        }
        else if(x3.equals(x4)){
            x=x3;
            BigFraction s1 = (y2.subtract(y1)).divide(x2.subtract(x1));
            y = s1.multiply(x.subtract(x1)).add(y1);
        }
        else{
            BigFraction s1 = (y2.subtract(y1)).divide(x2.subtract(x1));
            BigFraction s2 = (y4.subtract(y3)).divide(x4.subtract(x3));
            //x = (x1*(x4*(y3-y2)+x3*(y2-y4))+x2*(x4*(y1-y3)+x3*(y4-y1)))/(-(x3-x4)*(y1-y2)+(x1-x2)*(y3-y4));
            x = (x1.multiply(x4.multiply(y3.subtract(y2)).add(x3.multiply(y2.subtract(y4))) ).add(x2.multiply(x4.multiply(y1.subtract(y3) ).add(x3.multiply(y4.subtract(y1) )) ))).divide(((x4.subtract(x3)).multiply(y1.subtract(y2)).add((x1.subtract(x2) ).multiply(y3.subtract(y4)))));
            //y = s1*(x-x1)+y1;
            y = s1.multiply(x.subtract(x1)).add(y1);

        }
       
        return new Point(x, y, a);
    }
	
	//creates a random line segment that intersects atleast one line segment
	public static LineSegment randomSeg(ArrayList<LineSegment> segments, int linenum){
		Point pointa = chooseFirstPt();
		Point pointb = chooseSecondPt(pointa);
		if(isLegal(pointa, pointb)){			
			return new LineSegment(("s"+Integer.toString(linenum)),
					pointa.getX(), pointa.getY(), pointb.getX(), pointb.getY());
		}
		else{
			return randomSeg(segments, linenum);
		}
	}
	
	//creates a line segment between two vertices
	public static LineSegment vertToVert(ArrayList<LineSegment> t_segments, int linenum){
		ArrayList<LineSegment> segments = new ArrayList<LineSegment>(t_segments);
			System.out.println(segments.size()); // delete me!!

		
		int indexA = rdm.nextInt(segments.size());
		LineSegment segA = segments.get(indexA);
		segments.remove(indexA);
		
		LineSegment segB = segA;
		
		//find a pair of intersecting lines
		boolean pairNotFound = true;
		while(pairNotFound){
			int indexB;
			if(segments.size()<=0){
				indexB = 0;
			}
			else{
				 indexB = rdm.nextInt(segments.size());
			}
			segB = segments.get(indexB);
			segments.remove(indexB);
			
			if(doIntersect(segA, segB)){
				pairNotFound = false;
			}
		}
		
		//find their intersection point
		Point firstpt = intersection(segA, segB);	
		
		//initialize C and D
		segments = t_segments;
		segments.remove(indexA);		
		LineSegment segC = segB;		
		segments.remove(segB);
		int indexD;
		if(segments.size()<=0){
			indexD = 0;
		}
		else{
			 indexD = rdm.nextInt(segments.size());
		}
		LineSegment segD = segments.get(indexD);
		segments.remove(indexD);
		
		//find two line segments that intersect, and are not A or B
		//unless there are no separate intersecting segments, in which case
		//C becomes B
		boolean notChosen = true;
		while(notChosen && !segments.isEmpty()){
			int indexC;
			if(segments.size()<=0){
				indexC = 0;
			}
			else{
				 indexC = rdm.nextInt(segments.size());
			}
			
			segC = segments.get(indexC);
			segments.remove(indexC);
			
			if(doIntersect(segC, segD)){
				notChosen = false;
			}
			else{ segC = segB;}
		}
		
		//find intersection of C and D
		Point secpt = intersection(segC, segD);		
		
		//create segment based on intersection
		if(isLegal(firstpt, secpt)){
			return new LineSegment(("s"+Integer.toString(linenum)),
					firstpt.getX(), firstpt.getY(), secpt.getX(), secpt.getY());
		}
		else{
			return randomSeg(t_segments, linenum);
		}
		
	}
	
	// vertex to a random segment
	public static LineSegment randomToVert(ArrayList<LineSegment> t_segments, int linenum) {

		ArrayList<LineSegment> segments = new ArrayList<LineSegment>(t_segments);
		System.out.println(segments.size()); // delete me!!

		int indexA;
		if (segments.size() <= 0) {
			indexA = 0;
		} else {
			indexA = rdm.nextInt(segments.size());
		}
		LineSegment segA = segments.get(indexA);
		segments.remove(indexA);
		LineSegment segB = segA;

		// find a pair of intersecting lines
		boolean pairNotFound = true;
		while (pairNotFound) {
			int indexB;
			if (segments.size() <= 0) { //remember to delete me all of this stuff
				indexB = 0;
			} else {
				indexB = rdm.nextInt(segments.size());
			}
			segB = segments.get(indexB);
			segments.remove(indexB);
			if (doIntersect(segA, segB)) {
				pairNotFound = false;
			}
		}

		// find their intersection point
		Point firstpt = intersection(segA, segB);

		// create segment based on intersection
		Point secpt = chooseSecondPt(firstpt);
		if (isLegal(firstpt, secpt)) {
			return new LineSegment(("s" + Integer.toString(linenum)), firstpt
					.getX(), firstpt.getY(), secpt.getX(), secpt.getY());
		} else {
			return randomToVert(t_segments, linenum);
		}

	}
	
	
	
	
	//min and max methods for BigFraction	
	public static BigFraction Max(BigFraction a, BigFraction b){
		if(a.compareTo(b)==1){
			return a;
		}
		else{
			return b;
		}
	}
	
	public static BigFraction Min(BigFraction a, BigFraction b){
		if(a.compareTo(b)==-1){
			return a;
		}
		else{
			return b;
		}
	}
	
}//end class
